COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\rm
C00005 ENDMK
C⊗;
\rm
\magnification=\magstephalf
\input today.tex

\rightline{CS 259 (now 358)}

\vskip .25in

On a certain planet, where the ``people'' are immortal, there
is only one policeman. He keeps a list, ranking the residents
by priority for observation. Every day, he enters all new
births at the bottom of his list. He arrests the culprit
nearest to the top of the list who commits a crime on that
day (the statute of limitations applies on the next day).
A judge fines the culprit \$15 and releases him. The
policeman moves that name to the bottom of the list.	
We prove that everybody who commits crimes on infinitely
many days (the definition of a professional criminal)
gets punished infinitely often.

Starting on any particular day, by induction on a person's
rank on that day's list, we show everyone eventually is
punished or goes straight (commits no more crimes).
Above the $i↑{th}$ person, there are $i-1$ others, who
eventually all are punished or go straight. Those who
are punished have their names moved below Mr.~X's;
when all of them have been punished, if X hasn't, all
the names remaining above Mr.~X's have gone straight.
If he has not gone straight, he will be punished for
his next crime. If he commits crimes on infinitely many
days, he never goes straight, so he gets punished after
any designated day, i.e. infinitely often.

\vfil\end